/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2025-02-07
 * Time: 14:24
 */
class Solution1 {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length+1];
        int ret = Integer.MIN_VALUE;
        for(int i = 1 ; i <= nums.length ; i++){
            dp[i] = Math.max(nums[i-1] , dp[i-1]+nums[i-1]);
            ret = Math.max(ret,dp[i]);
        }
        for (int x : dp){
            System.out.print(x);
        }
        return ret;
    }
}
public class Test1 {
    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        solution1.maxSubArray(nums);
    }
}
